package com.jml.排序;


/**
 * @author:jml
 * @date: 2020/3/28 0028 11:42
 * @description：是基于插入排序的改进 通过加大插入元素之间的间隔，并对这些间隔的元素进行插入排序 从而使得数据可以大幅度的移动，当完成该间隔的排序后，
 * 希尔排序会减少间隔继续排序，依次进行下去 间隔缩小到1的时候就是插入排序，这样就不会有大的数据移动，保证右边不会有特别小的数据。
 *
 * 间隔的计算： 间隔h的初始值为1，通过h=3*h+1来计算循环，直到间隔大于数组的大小停止。最大间隔为不大于数组大小的最大值 最大间隔就是间隔的初始值
 *
 * 间隔的减少：h=(h-1)/3
 *
 *
 * 1, 3, 2, 45, 65, 33, 12
 * 间隔为4
 * 1            65
 *    3             33
 *       2               12
 *缩小间隔为（4-1）/3 = 1
 *
 *
 * 1, 3, 2, 45, 65, 33, 12 , 0, 12, 100, 5
 * 计算h间隔为4
 * 1            65              12
 *              得到
 * 1            12              65
 * -------------------------------------------
 *    3             33              100
 *              得到
 *    3             33              100
 * -------------------------------------------
 *         2            12               5
 *              得到
 *         2            5                12
 * -------------------------------------------
 *           45            0
 *              得到
 *            0             45
 * -------------------------------------------
 * 上面4次排序得到
 * 1, 3, 2, 0, 12, 33, 5, 45, 65, 100, 12
 * 此时h为1
 * 对这一列进行间隔为1的插入排序
 *
 */
public class 希尔排序 {

    public static void main(String[] args) {
        long[] arr = {1, 3, 2, 45, 65, 33, 12,0,12,100,5};
        sort(arr);
    }

    private static void sort(long[] arr) {
        //初始化一个间隔
        int h = 1;
        //计算最大间隔
        while (h < arr.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            //进行插入排序,间隔为h
            for (int i = 0; i < arr.length; i = i + 1) {
                //这里条件设置为j >= h 而不是j>0,因为会存在j-h<0,arr[j-h]就会索引越界
                //存在等号的极限就是j往前移动，和第一个元素比较，所以需要j=h
                for (int j = i + h; j >= h && j < arr.length; j = j - h) {
                    if (arr[j] < arr[j - h]) {
                        long temp = arr[j];
                        arr[j] = arr[j - h];
                        arr[j - h] = temp;
                    } else {
                        //因为前面的都是已经排好序的，如果arr[j] > arr[j - h] 则前面的所有数都小于a[j]
                        break;
                    }
                }
            }
            //减小间隔
            h = (h - 1) / 3;
        }
        //打印
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }


}
